package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/*
1.计算出子节点到树根的高度，如果高度差大于1 false

*/

type Queue struct {
	Head *QueueNode
	Tail *QueueNode
}

type QueueNode struct {
	Data *TreeNode
	Next *QueueNode
}

func NewQueueNode(data *TreeNode) *QueueNode {
	return &QueueNode{Data: data, Next: nil}
}

func InsertQueue(queue *Queue, data *TreeNode) {
	if queue.Head == nil {
		queue.Head = NewQueueNode(data)
		queue.Tail = queue.Head
	} else {
		qNode := NewQueueNode(data)
		queue.Tail.Next = qNode
		queue.Tail = qNode
	}
}

func PopQueue(queue *Queue) *TreeNode {
	if queue == nil {
		return nil
	}
	if queue.Head == nil {
		return nil
	}
	if queue.Head == queue.Tail {
		node := queue.Head
		queue.Head = nil
		queue.Tail = nil
		return node.Data
	}
	node := queue.Head
	queue.Head = queue.Head.Next
	return node.Data
}

func IsEmpty(queue *Queue) bool {
	if queue == nil {
		return true
	}
	if queue.Head == nil {
		return true
	}
	return false
}

func isCompleteTree(root *TreeNode) bool {
	if root == nil {
		return true
	}
	queue := Queue{}
	InsertQueue(&queue, root)
	//1.跟节点入队列
	/*
		从队列取一个数据加入打印结果数组
		如果左右节点都不为空加入队列，继续循环
		如果左节点为空
	*/
	nilCount := 0
	for !IsEmpty(&queue) {
		node := PopQueue(&queue)
		if node != nil {
			fmt.Println(node.Val)
			if nilCount != 0 {
				return false
			}
		} else {
			//遇到空了过后不能遇到数字
			fmt.Println("nil")
			nilCount = 1
			continue
		}
		InsertQueue(&queue, node.Left)
		InsertQueue(&queue, node.Right)
	}
	return true
}

func main() {
	//b := TreeNode{Val: 1}
	t1 := TreeNode{Val: 1}
	t2 := TreeNode{Val: 3, Left: nil, Right: &t1}
	//t2 := TreeNode{Val: -1 << 31}
	//l:=lenTree(&t2)
	//fmt.Println(l)
	isCompleteTree(&t2)
}
